"""
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组.
"""
def threeSum(nums):
    n = len(nums)
    nums.sort()
    ans = []
    # a+b+c=0,一个个去找
    # 找出a,
    for i in range(n):
        # 如果 i 大于 0 并且 nums[i] 等于 nums[i - 1]，说明这个 a 的值已经被考虑过了，为了避免重复，跳过当前循环。
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        # c 对应的指针初始指向数组的最右端
        third = n - 1
        target = -nums[i]  # 相加为零
        for j in range(i + 1, n):
            # 如果 j 大于 i + 1 并且 nums[j] 等于 nums[j - 1]，说明这个 b 的值已经被考虑过了，为了避免重复，跳过当前循环。
            if j > i + 1 and nums[j] == nums[j - 1]:
                continue
            # 使用 while 循环，通过移动 third 的位置和判断 nums[j] + nums[third] 是否大于 target 来找到满足条件的 b 和 c。如果 j 和 third 指向同一个位置，说明已经找完所有可能的 b 和 c 组合，结束本次循环。
            while j < third and nums[j] + nums[third] > target:
                third -= 1
            # 如果指针重合，随着 b 后续的增加
            # 就不会有满足 a+b+c=0 ，可以退出循环
            if j == third:
                break
            if nums[j] + nums[third] == target:
                ans.append([nums[i], nums[j], nums[third]])

    return ans
